package com.cty.twentiethDay;

import java.util.HashSet;

/*
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。
*/
public class Q_26 {
    public static void main(String[] args) {

    }

    // 方法一:迭代 跟上一题的做法一样
    /*
     * 时间复杂度O(n) 空间复杂度O(n)
     * */
    public static ListNode detectCycle(ListNode head) {
        HashSet<ListNode> listNodes = new HashSet<>();
        ListNode temp = head;
        while (temp != null) {
            if (!listNodes.add(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    // 力扣官方题解 快慢指针
    /*
     * 思路:
     *   我们让快指针和慢指针都从初始点出发 慢指针走一步 快指针走两步
     *   假设 他们在某一点相遇 此时 慢指针在环中走了 b 的距离 环剩下的距离为 c
     *   环外的距离为a 我们假设此时快指针走了n圈 得出快指针走的距离：
     *   a + n (b + c) + b = a + nc + (n + 1) b
     *   此时快指针走的距离 是慢指针走的距离的两倍
     *   得出公式 2(a + b) = a + nc +(n + 1) b
     *   化简 a = (n  - 1) b + nc => a = c + (n - 1)(b + c)
     *   此公式说明 当快指针与慢指针相遇时 此时我们让慢指针继续向前走
     *   新定义一个指针从头开始走 二者速度一样 当二者相遇时 正是刚进
     *   入环的那个节点 此时满指针 走了 c + (n - 1)(b + c)
     *   新指针走了 a
     *   时间复杂度O(n) 空间复杂度O(1)
     * */
    public static ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode newTemp = head;
                while (newTemp != slow) {
                    newTemp = newTemp.next;
                    slow = slow.next;
                }
                return newTemp;
            }
        }
        return null;
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
